package com.demo.leetcode;

import java.util.HashMap;
import java.util.Map;

public class LRUCache<K, V> {

    private int capacity;
    private int size;
    private Map<K, Node<K, V>> nodeMap = new HashMap<K, Node<K, V>>();
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;

        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.pre = head;
    }

    public void put(K key, V value) {
        Node<K, V> oldNode = nodeMap.get(key);
        if (oldNode == null) {
            if (size >= capacity) {
                //移除一个节点
                removeNode();
            }
            oldNode = new Node<K, V>(key, value);
            addToHead(oldNode);
            nodeMap.put(key, oldNode);
            size++;

        } else {
            //移动到头部节点
            removeFromList(oldNode);
            addToHead(oldNode);
        }
    }

    public Node get(K key) {
        Node<K, V> node = nodeMap.get(key);
        if (node != null) {
            removeFromList(node);
            addToHead(node);
        }
        return node;
    }

    private void addToHead(Node node) {
        Node next = head.next;
        head.next = node;
        next.pre = node;

        node.pre = head;
        node.next = next;
    }

    /**
     * 从尾部删除一个节点
     */
    private void removeNode() {
        Node node = tail.pre;
        //从链表删除这个节点
        removeFromList(node);

        nodeMap.remove(node.key);
        size--;
    }

    private void removeFromList(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;

        node.pre = null;
        node.next = null;
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(5);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);
        lruCache.put(5,5);
        lruCache.put(6,6);
        System.out.println(lruCache.get(1));


    }

}

class Node<K, V> {
    K key;
    V value;
    Node pre;
    Node next;

    public Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}
